package oct2013;

public class SpiralMatrixII {
	int[][] matrix;
	int cnt;

	public int[][] generateMatrix(int n) {
		matrix = new int[n][n];
		cnt = 1;
		dfs(0, n - 1);
		return matrix;
	}

	void dfs(int i, int j) {
		if (i > j)
			return;
		if (i == j) {
			matrix[i][j] = cnt++;
			return;
		}
		for (int k = i; k < j; ++k) {
			matrix[i][k] = cnt++;
		}
		for (int k = i; k < j; ++k) {
			matrix[k][j] = cnt++;
		}
		for (int k = j; k > i; --k) {
			matrix[j][k] = cnt++;
		}
		for (int k = j; k > i; --k) {
			matrix[k][i] = cnt++;
		}
		dfs(i + 1, j - 1);
	}

}
